package 树;

public class Leedcode572另一棵树的子树 {

    /**
     * 传入两个树,就能判断是否为另一棵树的子树
     * @param root
     * @param subRoot
     * @return
     */
    public boolean isSubtree(TreeNode root, TreeNode subRoot) {
        //如果两棵树都为空，则两个树相同，返回true
        if (root == null && subRoot == null) {
            return true;
        }
        //如果一颗子树为空，另一个树不为空，则说明两个树的高度不一致，则说明不是子树
        if (root == null || subRoot == null) {
            return false;
        }
        //否则比较当前两棵树是否为同一棵树，当前root树的左子树是否包含subRoot和当前root的右子树是否包含subroot
        return isSameTree(root, subRoot) || isSubtree(root.left, subRoot) || isSubtree(root.right, subRoot);
    }


    public boolean isSameTree(TreeNode p, TreeNode q) {

        //p，q同时为空，肯定是相同的树
        if (p == null && q == null) {
            return true;
        }
        //一个为空一个不为空，就不是相同的树
        if (p == null && q != null) {
            return false;
        }

        if (p != null && q == null){
            return true;
        }
        //走到这里说明两个树都不为空，判断两个树当前节点的值是否相等

        //在比较左右子树的是否相等，左右子树同时为true才是相同的树
        return (p.val == q.val && isSameTree(p.left, q.left) && isSameTree(p.right, q.right));
    }
}
